package 树.BST;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/*
解题思路：
    这题第一反应是直接遍历这个树，把元素出现的次数存入到一个HashMap中。但是这是一颗二叉搜索树，如果直接用HashMap效率太低了，可以考虑二叉搜索树的特性。
    我们用中序遍历，比如一次中序遍历后的结果为{0,0,1,2,5,6,6}。我们可以发现，只要是一个数出现多次，那么它必是连续的。
    ①所以考虑用一个base，来存放当前元素，当下一次遍历的时候，我们只要拿即将遍历的元root.val和base比较
    ②如果相等，证明它们是同一个元素，这样的话count++；证明这个元素出现的次数加一。
    ③如果不等，那么更新base为root.val，并且重置count=1；这样就是一个新的元素，目前出现次数为1.
    ④经过上面两步后，我们再用一个MaxCount来存放之前遍历过的所有元素其中 出现次数最多的那个次数（有点绕口，简单来说就是存放的是到目前为止“出现最多的次数”注意！存放的是次数而不是元素）。
    ⑤那当前元素的出现次数count和maxCount比较。
    ⑥维护一个List 名叫answer，来存放出现次数最多的元素
    ⑦如果等于maxcount，证明它的出现次数和maxcount相等，即该元素出现次数也是最多的。就把root.val加入到answer中去。
    ⑧如果大于maxCount，那么证明出现了新的最大次数，我们更新maxcount=count；并且清空原来的answer数组，再把现在的root.val--也即是出现次数最多的那个元素存放到answer中。
    ⑨所有递归完成后，只要answer存放的就是答案了，但是题目要求int[]，我们再在主函数中把answer转成int[]就可以了
*/
public class 二叉搜索树中的众数_501 {
    List<Integer> answer = new ArrayList<Integer>();
    int base, count, maxCount;//初始值都为0
    /*
    base：记录当前的数字
    count： 记录当前数字重复的次数
    maxCount： 维护已经扫描过的数当中出现最多的那个数字的出现次数
    answer： 记录出现次数最多的元素（会经常更新）。

    */

    public int[] findMode(TreeNode root) {
        figureout(root);//这个方法执行完以后answer存放的就是出现次数最多的  哪些元素

        int[] res=new int[answer.size()];
        for(int i=0;i<answer.size();i++){
            res[i]=answer.get(i);
        }

        return res;
    }


    public void figureout(TreeNode root){
        if(root==null){
            return ;
        }
        figureout(root.left);

        if(root.val==base){//如果下一个元素和base相等则count+1
            count++;
        }else{//不相等就更新base，然后把count恢复为1
            base=root.val;
            count=1;
        }

        if(count==maxCount){//如果该元素的出现次数  和maxcount相等，就把该元素放入anser中
            answer.add(root.val);
        }else if(count>maxCount){//当前元素的出现次数大于MAXcount ，则count变成最大次数
            maxCount= count;
            answer.clear();//清空原来的集合，因为有更大的次数了，answer中只存放最大次数的元素，原来的已经不是最大的，所以要清空。
            answer.add(root.val);//把新的“出现次数最多”的元素加入到anser中，以保证anser中总是存放的目前 “出现次数最多的”  数字

        }

        figureout(root.right);
    }
}
